package item03;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Lv Jing
 * @date 2018年07月10日 0:43
 */
public class Arr02 {

    /*
     * 题目二：不修改数组找出重复的数字 P.41
     * 思路：采用类似二分法的思路，由于题目给出的数组（长度为n+1）大小在1~n之间，所以至少有一个是重复的，把判断的轴分成两段，
     * 先看前半段的数在数组中能找到多少个，如果大于前半段的个数，则证明该区间是有重复的数；否则后半段就有重复的数。
     */

    private int getDuplication(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        int length = arr.length;
        int start = 1;
        int end = length - 1;

        while (end >= start) {
            // 找到中间位置
            int middle = ((end - start) >> 1) + start;

            int count = getCount(arr, start, middle);

            // 已二分到一个数
            if (end == start) {
                if (count > 1) {
                    return start;
                }
                return -1;
            }

            // 继续缩小二分范围
            if (count > (middle - start) + 1) {
                // 前半段存在重复数字，下次二分以前半段为基准
                end = middle;
            } else {
                // 前半段不存在，则根据题目需求，后半段必定存在
                start = middle + 1;
            }
        }
        return -1;
    }

    private int getCount(int[] arr, int start, int end) {
        int count = 0;
        // 遍历数组，找出在指定范围中的数字个数
        for (int value : arr) {
            if (value >= start && value <= end) {
                count++;
            }
        }
        return count;
    }

    /**
     * 空测试
     */
    @Test
    public void test01() {
        int duplication = getDuplication(null);
        Assert.assertEquals(duplication, -1);
    }

    /**
     * 不符合要求的数组测试
     */
    @Test
    public void test02() {
        int[] arr = {-1, 2, 2, 4};
        int duplication = getDuplication(arr);
        Assert.assertEquals(duplication, -1);
    }

    /**
     * 正常计算测试
     */
    @Test
    public void test03() {
        int[] arr = {4, 2, 3, 5, 3, 2, 8, 6};
        int duplication = getDuplication(arr);
        Assert.assertEquals(duplication, 3);
    }

    /**
     * 多个重复数字
     */
    @Test
    public void test04() {
        int[] arr = {4, 2, 3, 5, 3, 2, 8, 6, 6};
        int duplication = getDuplication(arr);
        Assert.assertEquals(duplication, 3);
    }
}
